package algorithm_demo.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 70. 爬楼梯
 * https://leetcode.cn/problems/climbing-stairs/
 *
 * @author Api
 * @date 2023/4/27 7:33
 */
public class Problem_070_ClimbingStairs {
    /*暴力递归*/
    int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    /*Map 备忘录*/
    static Map<Integer, Integer> tempMap = new HashMap<>();

    public static int climbStairs1(int n) {
        if (n == 0) {
            return 1;
        }
        if (n <= 2) {
            return n;
        }
        //判断有没有计算过，即看看备忘录有没有
        if (tempMap.containsKey(n)) {
            return tempMap.get(n);
        } else {
            //备忘录没有，即没有计算过，执行递归计算，并且把结果保存在备忘录map中
            tempMap.put(n, (climbStairs1(n - 1)) + climbStairs1(n - 2));
            return tempMap.get(n);
        }
    }

    //动态规划的核心思想就是拆分子问题，记住过往，减少重复计算
    //并且动态规划一般都是自底向上的，因此到这里，基于青蛙跳阶问题，我总结了一下我做动态规划的思路：
    /*
     * 穷举分析
     * 确定边界
     * 找出规律，确定最优子结构
     * 写出状态转移方程
     * */
    public static int climbStairs2(int n) {
        if (n <= 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int a = 1;
        int b = 2;
        int temp = 0;
        for (int i = 3; i <= n; i++) {
            temp = a + b;
            a = b;
            b = temp;
        }
        return temp;
    }

    /*
     * dp[0][0][...] = 边界值
     * for(状态1 ：所有状态1的值){
     *   for(状态2 ：所有状态2的值){
     *      for(...){
     *       //状态转移方程
     *       dp[状态1][状态2][...] = 求最值
     *      }
     *   }
     *  }
     * */

    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        //初始化就是边界情况
        dp[0] = 1;
        int maxAns = 1;
        //自底向上遍历
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            //从下标0到i遍历
            for (int j = 0; j < i; j++) {
                //找到前面比nums[i]小的数nums[j],即有dp[i]=dp[j]+1;
                if (nums[j]<nums[i]){
                    //因为会有多个小于nums[i]的数，也就是会存在多种组合了，我们取最大值放到dp[i]
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            //求出dp[i]后，dp最大那个就是nums的最长递增子序列
            maxAns = Math.max(maxAns, dp[i]);
        }
        return maxAns;
    }

    public static void main(String[] args) {
        int[] arr = {10,9,2,5,3,7,101,18};
        int i = lengthOfLIS(arr);
        System.out.println(i);
    }
}
